/**
 * https://leetcode.cn/submissions/detail/584141338/
 * 55. 跳跃游戏
 * Medium, 黄伟杰 2024.11.30
 * BFS
 */

class Solution
{
public:
    bool canJump(vector<int> &nums)
    {
        int n = nums.size() - 1;
        vector<bool> vis(n + 1, false);
        deque<int> dq; //<下标
        dq.push_back(0);
        while (!dq.empty())
        {
            auto p = dq.front();
            dq.pop_front();
            if (vis[p])
                continue;
            // int i = p;

            for (int i = 0; i <= nums[p]; i++)
            {
                if (p + i < n)
                    dq.push_back(p + i);
                else if (p + i == n)
                    return true;
            }

            vis[p] = true;
        }
        return false;
    }
};
